//There is an integer array nums sorted in ascending order (with distinct values
//). 
//
// Prior to being passed to your function, nums is rotated at an unknown pivot i
//ndex k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+
//1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, 
//[0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. 
//
// Given the array nums after the rotation and an integer target, return the ind
//ex of target if it is in nums, or -1 if it is not in nums. 
//
// You must write an algorithm with O(log n) runtime complexity. 
//
// 
// Example 1: 
// Input: nums = [4,5,6,7,0,1,2], target = 0
//Output: 4
// Example 2: 
// Input: nums = [6,7,0,1,2,3,4,5], target = 3
//Output: -1
// Example 3: 
// Input: nums = [1], target = 0
//Output: -1
// 
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5000 
// -104 <= nums[i] <= 104 
// All values of nums are unique. 
// nums is guaranteed to be rotated at some pivot. 
// -104 <= target <= 104 
// 
// Related Topics 数组 二分查找 
// 👍 1359 👎 0
package leetcode.editor.cn;

//Java：Search in Rotated Sorted Array
class P33SearchInRotatedSortedArray {
    public static void main(String[] args) {
        Solution solution = new P33SearchInRotatedSortedArray().new Solution();
        solution.search(new int[]{6, 7, 8, 9, 2, 3, 4, 5}, 3);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int len = right;

            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] == target) return mid;

                if (nums[mid] > nums[len]) {
                    // 二分查找应该在有序数组中进行，此时[left, mid)有序
                    if (target >= nums[left] && target < nums[mid]) {
                        // 如果在[left, mid)区间，则应该继续在[left, mid - 1)中继续查找
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    // 二分查找应该在有序数组中进行，此时(mid, right]有序
                    if (target > nums[mid] && target <= nums[right]) {
                        // 如果在(mid, right]区间，则应该继续在(mid + 1, right]中继续查找
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}